#include <stdio.h>
#include <string.h>

#include <iostream>
using std::cout;
using std::endl;

// 字符串(主串/单模式串)匹配

// 一、如果很小的串并且调用频率低，就BF暴力遍历比较

int CharHash(char ch) { return ch - 'a'; }

// 二、RK算法：求子串哈希（假定只包含a-z），再对比
// 简单，适用于小文本
const char* RabinKarp(const char* str, const char* pattern) {
  int strLen = strlen(str);
  int patternLen = strlen(pattern);
  cout << strLen << "," << patternLen << endl;

  int patternHash = 0;
  const char* p = pattern;
  for (p = pattern; *p != 0; p++) {
    patternHash += CharHash(*p);
  }
  cout << "patternHash:" << patternHash << endl;

  int strHash = 0;
  for (p = str; p + patternLen <= str + strLen; p++) {
    if (p == str) {
      for (int i = 0; i < patternLen; ++i) {
        strHash += CharHash(*(p + i));
      }
    } else {
      strHash -= CharHash(*(p - 1));
      strHash += CharHash(*(p + patternLen - 1));
    }
    if (strHash == patternHash) {
      if (strncmp(p, pattern, strlen(pattern)) == 0) return p;
    }
  }
  return NULL;
}

void TestRabinKarp() {
  const char* str = "abcdefg,hijklmn";
  const char* pattern = "def";
  const char* p = RabinKarp(str, pattern);
  if (p)
    printf("found:%s\n", p);
  else
    printf("not found!\n");
}

int main(int argc, const char* argv[]) { TestRabinKarp(); }